/**
 ** 概述：斐波那契数列算法
 ** 原理: 所谓的斐波纳契数列是指：

	前2个数是 0 和 1 。
	第 i 个数是第 i-1 个数和第i-2 个数的和。
	斐波纳契数列的前10个数字是：

	0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
 ** 限制: 无
 ** 时间复杂度: T(n) = O(n)
 **/
export function fibonacci(n) {
	// 注释采用的递归办法，逻辑没问题，但是时间复杂度为T(n)=O(2^n),无法接受
	/**if(n == 1){
		return 0;
	} else if(n == 2){
		return 1;
	} else {
		return fibonacci(n-1)+fibonacci(n-2);
	}**/
	// 此逻辑时间复杂度为T(n)=O(n),速度很快
	let index0 = 1;
	let index1 = 1;
	let result = 0;
	if(n == 2 || n == 3){
		result = 1;
	}
	for(let i = 3; i < n; i++){
		result = index0 + index1;
		index0 = index1;
		index1 = result;
	}
	return result;
}